/*
 * @lc app=leetcode.cn id=239 lang=golang
 *
 * [239] 滑动窗口最大值
 */

// 3. 优先队列
// @lc code=start
func maxSlidingWindow(nums []int, k int) []int {
	q := &hp{make([]int, k), nums}
	for i := 0; i < k; i++ {
		q.IntSlice[i] = i
	}
	heap.Init(q)

	n := len(nums)
	ans := make([]int, 1, n-k+1)
	ans[0] = nums[q.IntSlice[0]]
	for i := k; i < n; i++ {
		heap.Push(q, i)
		for q.IntSlice[0] <= i-k {
			heap.Pop(q)
		}
		ans = append(ans, nums[q.IntSlice[0]])
	}
	return ans
}

type hp struct {
	sort.IntSlice
	array []int
}

func (h *hp) Less(i, j int) bool {
	return h.array[h.IntSlice[i]] > h.array[h.IntSlice[j]]
}

func (h *hp) Push(v interface{}) {
	h.IntSlice = append(h.IntSlice, v.(int))

}
func (h *hp) Pop() interface{} {
	a := h.IntSlice
	v := a[len(a)-1]
	h.IntSlice = a[:len(a)-1]
	return v
}

// @lc code=end

// 2. 单调队列，双端队列
// 队列中存放是nums数组的下标，对应数组的值为从大到小排列，
// 即遍历数组时，当前值比队尾值大，弹出队尾（loop），直到队列弹空或小于队尾时入队，
// 				当前值比队尾值小，则直接入队
// 所以，队首的值永远为已遍历的nums数组的最大值，但此最大值在不在当前窗口中，还是未知
// 当前窗口边界为 [right-left+1, right]，包含左右两边的边界
// 只有当队首的值在此窗口之中时有效，否则就弹出队首(loop)，
// 直到队首的值此窗口之中时，此时队首的值为当前窗口的最大值
// @lc code=start
func maxSlidingWindow(nums []int, k int) (ans []int) {
	queue := []int{}

	for right := 0; right < len(nums); right++ {
		for len(queue) > 0 && nums[right] >= nums[queue[len(queue)-1]] {
			queue = queue[:len(queue)-1]
		}
		queue = append(queue, right)

		if right >= k-1 {
			for queue[0] < (right - k + 1) {
				queue = queue[1:]
			}
			ans = append(ans, nums[queue[0]])
		}
	}
	return
}

// @lc code=end

// 1. 暴力 超时
// @lc code=start
// func maxSlidingWindow(nums []int, k int) (ans []int) {
// 	for i := 0; i <= len(nums)-k; i++ {
// 		currentWindow := make([]int, k)
// 		for j := 0; j < k; j++ {
// 			currentWindow[j] = nums[i+j]
// 		}
// 		ans = append(ans, maxArr(currentWindow))
// 	}
// 	return
// }

func maxSlidingWindow(nums []int, k int) (ans []int) {
	for i := 0; i < len(nums)-(k-1); i++ {
		ans = append(ans, maxArr(nums[i:i+k]))
	}
	return
}

func maxArr(nums []int) int {
	maxVal := nums[0]
	for i := 1; i < len(nums); i++ {
		maxVal = max(maxVal, nums[i])
	}
	return maxVal
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

// @lc code=end

